#include <iostream>
#include "CppDLlist.h"

void Swap(ElementType* value1,ElementType* value2)
{
    ElementType temp = *value1;
    *value1 = *value2;
    *value2 = temp;
}

DoubleLinkNode::DoubleLinkNode(ElementType element)
{
    this->data = element;
    this->next = NULL;
    this->prev = NULL;
}

DoubleLinkNode::~DoubleLinkNode()
{
    this->next = NULL;
    this->prev = NULL;
}

DoubleLinkList::DoubleLinkList()
{
    this->CLearptr = NULL;
    this->head = this->tail = new DoubleLinkNode(NULL);
    this->len = 0;
}

DoubleLinkList::DoubleLinkList(void (*CLearptr)(ElementType))
{
    this->CLearptr = CLearptr;
    this->head = this->tail = new DoubleLinkNode(NULL);
    this->len = 0;
}

DoubleLinkList::~DoubleLinkList()
{
    while(this->head!=NULL)
    {
        DLNode* next = this->head->next;
        if((this->head->data!=NULL) && this->CLearptr !=NULL)
        {
            this->CLearptr(this->head->data);
        }
        free(this->head);
        this->head = next;
    }
    this->len = 0;
}

//尾插
void DoubleLinkList::InsertTail_DLList(ElementType element)
{
    DLNode* newnode = new DoubleLinkNode(element);
    this->tail->next = newnode;   //把尾指针的next指针指向new
    newnode->prev = this->tail;   //new的prev指向尾
    this->tail = newnode;         //让newcoden成为新的尾
    this->len++;                  //长度加一
}

//头插
void DoubleLinkList::InsertHead_DLList(ElementType element)
{
    DLNode* newnode = new DoubleLinkNode(element);

    if(this->len == 0)  //如果链表为空,head->next == NULL,没有前驱指针
    {
        InsertTail_DLList(element);  //这时候头插就是尾插
    }
    else
    {
        newnode->next = this->head->next;   //new的后驱指针指向第一个有效元素
        newnode->prev = this->head;         //new的前驱指针指向head
        this->head->next->prev = newnode;   //第一个有效元素的前驱指针指向new
        this->head->next = newnode;         //head的后驱指针指向new
        this->len++;                       //长度加一
    }
}

//按位置插
void DoubleLinkList::InsertByIndex_DLList(ElementType element,int index)
{
    DLNode* newnode = new DoubleLinkNode(element);  //创建节点


    if(index<0 || index>this->len)
    {
        std::cout<<"非法位置"<<std::endl; 
        return;
    }

    if(index == this->len)
    {
        InsertTail_DLList(element);
    }
    else
    {
        DLNode* TravelPoint = this->head;
        for(int i=0;i<index;i++)
        {
            TravelPoint = TravelPoint->next;
        }
        newnode->next = TravelPoint->next;
        newnode->prev = TravelPoint;
        TravelPoint->next->prev = newnode;
        TravelPoint->next = newnode;
        this->len++;
    }
}

//遍历
void DoubleLinkList::Travel_DLList(void(*funcptr)(ElementType))
{
    if(funcptr == NULL)
        return;
    DLNode* Travelpiont = this->head->next;
    while(Travelpiont!=NULL)
    {
        funcptr(Travelpiont->data);
        Travelpiont = Travelpiont->next;
    }
    std::cout<<std::endl;
}

//按位置删
void DoubleLinkList::RemoveByIndex_DLList(int index)
{
    if(index<0||index>=this->len)
    {
        std::cout<<"invalid position: "<<index<<" len: "<<this->len<<std::endl;
        return;
    }

    if(index == this->len-1)                 //防止next->prev不存在
    {
        DLNode* prevnode = this->tail->prev;

        prevnode->next = NULL;
        if(this->CLearptr!=NULL)
        {
            CLearptr(this->tail->data);
        }
        delete this->tail;

        this->tail = prevnode;
    }
    else
    {
        DLNode* TravelPoint = this->head;
        for(int i=0;i<index;i++)
        {
            TravelPoint = TravelPoint->next;
        }

        DLNode* freenode = TravelPoint->next;
        freenode->next->prev = TravelPoint;
        TravelPoint->next = freenode->next;
        if(this->CLearptr!=NULL)
        {
            CLearptr(freenode->data);
        }
        delete freenode;
    }
    this->len--;
}

//按值删
void DoubleLinkList::RemoveByElement_DLList(ElementType element,bool(*opreptr)(ElementType,ElementType))
{
    DLNode* TravelPoint = this->head;
    while(TravelPoint->next != NULL)
    {
        //下一个节点需要删除
        if(opreptr(TravelPoint->next->data,element) == true)
        {
            /*留下内存的地址，后续释放，防止内存泄漏*/
            DLNode* freenode = TravelPoint->next;
            TravelPoint->next = freenode->next;
            if(this->CLearptr != NULL)
            {
                CLearptr(freenode->data);
            }
            delete freenode;
            this->len--;
        }
        else
        {
            TravelPoint = TravelPoint->next;   //防止跳过连续出现的需要删除的数
        }
    }
}

//按位置查找
ElementType* DoubleLinkList::SearchByIndex_DLList(int index)
{
    if(index< 0 || index>=this->len)
    {
        printf("非法的查找位置!\n");
        return NULL; 
    }

    DLNode* TravelPoint = this->head->next; //从第一个有效的数据开始遍历
    for(int i=0;i<index;i++)
    {
        TravelPoint = TravelPoint->next;
    }

    return &TravelPoint->data;  //返回地址
}

//按值查找
DoubleLinkList DoubleLinkList::SearchByElement_DLList(ElementType element,bool(*opreptr)(ElementType,ElementType))
{
    DoubleLinkList result = DoubleLinkList(this->CLearptr);
    DLNode* TravelPoint = this->head;
    while(TravelPoint->next != NULL)
    {
        //下一个节点需要删除
        if(opreptr(TravelPoint->next->data,element) == true)
        {
            result.InsertTail_DLList(TravelPoint->next->data);
        }
        TravelPoint = TravelPoint->next;   //防止跳过连续出现的需要删除的数
    }
    return result;
}

void DoubleLinkList::FastSort_DLList(DLNode* start,DLNode* end,bool(*funcptr)(ElementType,ElementType))
{
    if(start == end)
    {
        return;
    }
    DLNode* p1 = start;
    DLNode* p2 = start->next;

    while(p2!=end)
    {
        if(funcptr(p2->data,start->data)==true)
        {
            p1 = p1->next;
            Swap(&p1->data,&p2->data);
        }
        p2 = p2->next;
    }
    //退出循环的时候p2已经是空了
    Swap(&start->data,&p1->data);

    FastSort_DLList(start,p1,funcptr);
    FastSort_DLList(p1->next,p2,funcptr);

}

void DoubleLinkList::DLListSort(bool(*funcptr)(ElementType,ElementType))
{
    FastSort_DLList(this->head->next,this->tail->next,funcptr);
}

DoubleLinkNode* DoubleLinkList::GetListHead()
{
    return this->head;
}
